package com.chilly.vidio.study.leetcode;

import java.util.Arrays;
import java.util.Vector;

/**
 * 283. 移动零
 * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
 * 说明:
 * <p>
 * 必须在原数组上操作，不能拷贝额外的数组。
 * 尽量减少操作次数。
 *
 * @author Chilly Cui
 * @createDate 2021/2/27
 */
public class No283MoveZeroes {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {0, 1, 0, 3, 12};

        solution.moveZeroes(nums);
        System.out.println(Arrays.toString(nums));
        //[1, 3, 12, 0, 0]

        solution.moveZeroes2(nums);
        System.out.println(Arrays.toString(nums));
        //[1, 3, 12, 0, 0]

        solution.moveZeroes3(nums);
        System.out.println(Arrays.toString(nums));
        //[1, 3, 12, 0, 0]

        solution.moveZeroes4(nums);
        System.out.println(Arrays.toString(nums));
        //[1, 3, 12, 0, 0]

        solution.moveZeroes5(nums);
        System.out.println(Arrays.toString(nums));
        //[1, 3, 12, 0, 0]
    }

    static class Solution {
        //moveZeroes4 的优化空间：如果是数组中都是非0元素的话，相当于自己与自己交换
        public void moveZeroes5(int[] nums) {
            int k = 0;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] != 0) {
                    if (i != k) {
                        swap(nums, k++, i);
                    } else {
                        k++;
                    }
                }
            }
        }

        //0与非0的元素交换
        public void moveZeroes4(int[] nums) {
            int k = 0;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] != 0) {
                    swap(nums, k++, i);
                }
            }
        }

        //快慢指针：0与非0的元素交换
        public void moveZeroes3(int[] nums) {
            int n = nums.length, left = 0, right = 0;
            while (right < n) {
                if (nums[right] != 0) {
                    swap(nums, left, right);
                    left++;
                }
                right++;
            }
        }

        public void moveZeroes2(int[] nums) {
            int k = 0;
            //nums 中 [0,k)的元素均为非0
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] != 0) {
                    nums[k++] = nums[i];
                }
            }
            //将nums的剩余位置置为0
            for (int i = k; i < nums.length; i++) {
                nums[i] = 0;
            }
        }


        private void swap(int[] nums, int left, int right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
        }

        //使用额外的空间：先把非0的调出来，再把其余的置为0
        public void moveZeroes(int[] nums) {
            Vector<Integer> nonZeroElements = new Vector<>();
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] != 0) {
                    nonZeroElements.add(nums[i]);
                }
            }
            for (int i = 0; i < nonZeroElements.size(); i++) {
                nums[i] = nonZeroElements.get(i);
            }

            for (int i = nonZeroElements.size(); i < nums.length; i++) {
                nums[i] = 0;
            }
        }
    }
}
